<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Fibonacci Numbers</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.0">
<link rel="up" href="../number_series.html" title="Number Series">
<link rel="prev" href="primes.html" title="Prime Numbers">
<link rel="next" href="../sf_gamma.html" title="Gamma Functions">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="primes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../number_series.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_gamma.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.number_series.fibonacci_numbers"></a><a class="link" href="fibonacci_numbers.html" title="Fibonacci Numbers">Fibonacci
      Numbers</a>
</h3></div></div></div>
<p>
        <a href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_top">Fibonacci numbers</a>
        (F<sub>n</sub>) follows the linear recurrence F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub> starting with F<sub>0</sub>=0, F<sub>1</sub>=1.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h0"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.synopsis"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.synopsis">Synopsis</a>
      </h5>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span> <span class="special">{</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Policy</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">)</span> <span class="comment">// Checked version (default policy)</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Policy</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">Policy</span> <span class="special">&amp;</span><span class="identifier">pol</span><span class="special">)</span> <span class="comment">// Checked version (policy for errors etc.)</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">unchecked_fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">noexcept</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">is_fundamental</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">value</span><span class="special">);</span> <span class="special">{</span>  <span class="comment">// Unchecked version (no policy).</span>

<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
        The functions return F<sub>n</sub> for a given input <code class="literal">n</code> having type
        <code class="literal">T</code>.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h1"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.description"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.description">Description</a>
      </h5>
<p>
        The checked versions checks for the overflow before starting the computation.
        If <code class="literal">n</code> is so large that the result can not be represented
        in type <code class="literal">T</code>, it then calls <a class="link" href="../error_handling.html#math_toolkit.error_handling.overflow_error">overflow_error</a>.
        The overflow check is susceptible to off-by-one errors around the overflow
        limit. See Binet's Formula below for more details on the check.
      </p>
<p>
        These functions are all <code class="computeroutput"><span class="keyword">constexpr</span></code>
        from C++14 onwards, and in addition <code class="computeroutput"><span class="identifier">unchecked_fibonacci</span></code>
        is <code class="computeroutput"><span class="keyword">noexcept</span></code> when T is a fundamental
        type.
      </p>
<p>
        The final <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
        be used to control the behaviour of the function: how it handles errors,
        what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">policy
        documentation for more details</a>.
      </p>
<p>
        If in the checked version, the overflow check succeeds then the unchecked
        version is called which computes the desired F<sub>n</sub>. Checked version is slower
        because of the overhead involved in overflow check.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h2"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.generator"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.generator">Generator</a>
      </h5>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">fibonacci_generator</span> <span class="special">{</span>
  <span class="comment">// returns consecutive fibonacci number starting from 0, 1, 1, 2, ...</span>
  <span class="identifier">T</span> <span class="keyword">operator</span><span class="special">()();</span>
  <span class="comment">// reset the generator to start from nth fibonacci number</span>
  <span class="keyword">void</span> <span class="identifier">set</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">);</span>
<span class="special">}</span>
</pre>
<p>
        The generator returns consecutive fibonacci numbers starting with 0, 1, 1,
        2...
      </p>
<p>
        The state of the generator can be modified using <code class="literal">set()</code>
        which makes generator return consecutive fibonacci numbers starting from
        <code class="literal">n</code>[sup th] fibonacci number.
      </p>
<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">fibonacci_generator</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">gen</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">x</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// x is 0</span>
<span class="keyword">int</span> <span class="identifier">y</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// y is 1</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">5</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="comment">// this loop is same as gen.set(7);</span>
    <span class="identifier">gen</span><span class="special">();</span>
<span class="keyword">int</span> <span class="identifier">z</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// z is 13 </span>
</pre>
<p>
        Generator is non-throwing for all fundamental types and will not check for
        overflows.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h3"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.type_requirements"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.type_requirements">Type
        Requirements</a>
      </h5>
<p>
        The type must be an arithmetic type supporting +, -, * and can be initialized
        from trivial integral types.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h4"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.example"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.example">Example</a>
      </h5>
<p>
        The file <a href="../../../../example/reciprocal_fibonacci_constant.cpp" target="_top">reciprocal_fibonacci_constant.cpp</a>
        uses <code class="computeroutput"><span class="identifier">fibonacci_generator</span></code>
        to calculate the reciprocal fibonacci constant to 1000 digit precision like
        so:
      </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">multiprecision</span><span class="special">/</span><span class="identifier">mpfr</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iomanip</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>

<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> <span class="special">{</span>
    <span class="keyword">using</span> <span class="identifier">Real</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">multiprecision</span><span class="special">::</span><span class="identifier">mpfr_float_1000</span><span class="special">;</span>
    <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">fibonacci_generator</span><span class="special">&lt;</span><span class="identifier">Real</span><span class="special">&gt;</span> <span class="identifier">gen</span><span class="special">;</span>
    <span class="identifier">gen</span><span class="special">.</span><span class="identifier">set</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> <span class="comment">// start producing values from 1st fibonacci number</span>
    <span class="identifier">Real</span> <span class="identifier">ans</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>
    <span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">ITR</span> <span class="special">=</span> <span class="number">1000</span><span class="special">;</span>
    <span class="keyword">for</span> <span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="identifier">ITR</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{</span>
        <span class="identifier">ans</span> <span class="special">+=</span> <span class="number">1.0</span> <span class="special">/</span> <span class="identifier">gen</span><span class="special">();</span>
    <span class="special">}</span>
    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">setprecision</span><span class="special">(</span><span class="number">1000</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">"Reciprocal fibonacci constant after "</span>
              <span class="special">&lt;&lt;</span> <span class="identifier">ITR</span> <span class="special">&lt;&lt;</span> <span class="string">" iterations is: "</span> <span class="special">&lt;&lt;</span> <span class="identifier">ans</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h5"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.implementation"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.implementation">Implementation</a>
      </h5>
<p>
        The time complexity for computing fibonacci number is O(log n), without considering
        the time complexities of multiplication and addition (where <code class="literal">n</code>
        is the input parameter). The implementation is iterative version of <a href="http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF" target="_top">Dijkstra's identities</a>
        and which simply walks down the bits of <code class="literal">n</code>.
      </p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h6"></a>
        <span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.binet"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.binet">Binet's
        Formula</a>
      </h5>
<p>
        There is a closed form expression for computing fibonacci numbers but since
        it suffers from imprecision issues (using floating point computation), it
        is not implemented.
      </p>
<p>
        However an approximate formula is used for the overflow checking in the checked
        version.
      </p>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="primes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../number_series.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_gamma.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
